		Esse trabalho aborda o Problema da \'Arvore Geradora M\'inima Generalizada com Coleta de Pr\^emios (PAGMGCP), que,
 como o nome sugere, \'e uma generaliza\c c\~ao do cl\'assico Problema da \'Arvore Geradora M\'inima. O PAGMGCP pode ser definido sobre
um grafo n\~ao-direcionado $G(V,E)$ onde $V$ representa o conjunto de v\'ertices e $E$ o conjunto de arestas. Cada aresta $e \in E$ 
possui associado um custo $c_e \in R^{+}$ e cada v\'ertice $v \in V$ possui associado um pr\^emio $p_v \in R^{+}$. 
Neste problema, o conjunto de v\'ertices \'e particionado em $m$ grupos disjuntos
e n\~ao vazios $V_1, V_2,...,V_m$ e o objetivo \'e determinar uma \'arvore de custo m\'inimo que cubra pelo menos um 
v\'ertice de cada grupo e que a soma dos pr\^emios seja maior ou igual a um pr\^emio m\'inimo $P_{min}$.

		O PAGMGCP \'e uma variante do Problema da \'Arvore Geradora M\'inima Generalizada, onde o objetivo tamb\'em \'e
encontrar uma \'arvore de custo m\'inimo que cubra pelo menos um v\'ertice de cada grupo. Ainda relacionado a 
esse problema, existe uma outra vers\~ao onde deve-se cobrir exatamente um v\'ertice de cada grupo, para a qual \cite{ferreira:07}
desenvolveu abordagens heur\'isticas.
	%Fazer aplicacao do problema
	%Fazer revisao bibliografica

	O presente trabalho tem como objetivo propor uma maneira de aplicar busca local na meta-heur\'istica GRASP misturando
os conceitos de Melhor Melhora e Primeira Melhora, e assim encontrar limites primais para o PAGMGCP. A segunda
proposta desse trabalho \'e um algoritmo de separa\c c\~ao para encontrar limites duais. 
Para os limites duais foi feita uma reformula\c c\~ao do problema, pois 
dessa forma o algoritmo de separa\c c\~ao ficou mais eficiente. Para a restri\c c\~ao de pr\^emio m\'inimo s\~ao adicionados cortes de cobertura ao longo do algoritmo de separa\c c\~ao.


